package LeetCode._01算法入门.day10递归回溯;

import org.junit.Test;
import utils.MyPrintUtil;

/**
 * @author 挚爱之夕
 * @date 2022-03-01 - 03 - 01 - 21:50
 * @Description 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * @Version 简单
 */
public class _206反转链表 {
    static ListNode head;

    static {
        head = new ListNode(1);
        ListNode p = head;
        for (int i = 2; i < 6; i++) {
            p.next = new ListNode(i);
            p = p.next;
        }
    }

    //by me
    //1.递归
    @Test
    public void solve() {
        MyPrintUtil.printSingleLinkedList(head);
        System.out.println("\n----------------------");
        ListNode res = reverseList(head);
        MyPrintUtil.printSingleLinkedList(res);
    }

    public ListNode reverseList(ListNode head) {
        //考虑空链表和仅有一个节点的情况
        if (head == null || head.next == null)
            return head;
        //1.找到最后一个节点
        ListNode newHead = reverseList(head.next);
        //2.反转：让节点的下一个节点指向该节点（对尾节点除外的都执行该操作）
        head.next.next = head;
        //3.头结点的next赋值为null
        head.next = null;//如果不加此句，第一个节点和第二节点会产生环
        return newHead;
    }

    //2.迭代
    public ListNode reverseList1(ListNode head) {
        ListNode cur;   //pre的下一个节点
        ListNode pre;   //cur的前一个节点
        ListNode p;     //辅助节点
        pre = null;
        cur = head;
        while (cur != null) {
            //记录cur的下一个节点
            p = cur.next;
            //翻转
            cur.next = pre;
            //pre和cur都向后移一位
            pre = cur;
            cur = p;
        }
        //循环结束后，pre原链表的最后一个节点，新链表的表头
        return pre;
    }
}
